//package work.rightAnswer;
//
//import java.util.HashMap;
//
//
////模仿LinkedHashMap的原理：哈希表+双链表
////HashMap<Integer,DLinkedNode> key为int类型 value为双链表节点
////双链表节点的属性 pre next value 这几个关键属性，再通过定义头节点与尾节点。
//// 可以实现已知双链表节点，实现o（1）时间的删除，新增节点
////另外，定义size 和 capacity 记录大小和容量
//class LRUCache_146 {
//
//    class DLinkedNode{
//        int key;
//        int value;
//        DLinkedNode pre;
//        DLinkedNode next;
//
//        public DLinkedNode(int key,int value) {
//            this.key = key;
//            this.value = value;
//        }
//
//        public DLinkedNode() {
//        }
//    }
//
//    HashMap<Integer,DLinkedNode> hashMap;
//    DLinkedNode head;
//    DLinkedNode tail;//尾节点放置最久没被使用的节点
//    int size;
//    int capacity;
//
//    public LRUCache_146(int capacity) {
//        hashMap = new HashMap<>();
//        head = new DLinkedNode();
//        tail=  new DLinkedNode();
//        head.next = tail;
//        tail.pre = head;
//        size = 0;
//        this.capacity = capacity;
//    }
//
//    public int get(int key) {
//        if(!hashMap.containsKey(key)){
//            return -1;
//        }
//        //获得value值返回，并把当前节点删除，在表头新增
//        DLinkedNode dLinkedNode = hashMap.get(key);
//        removeNode(dLinkedNode);
//        addNodeToHead(dLinkedNode);
//        return dLinkedNode.value;
//    }
//
//    public void put(int key, int value) {
//        DLinkedNode dLinkedNode = new DLinkedNode(key,value);
//        //如何有key 那么替换 更新节点链表位置
//        if(hashMap.containsKey(key)){
//            DLinkedNode node = hashMap.get(key);
//            removeNode(node);
//            hashMap.put(key,dLinkedNode);
//            addNodeToHead(dLinkedNode);
//            return;
//        }
//        //不含key的话
//        //判断size==capacity
//        if(size==capacity){//删除尾节点（最久未使用节点）
//            hashMap.remove(tail.pre.key);
//            removeNode(tail.pre);
//            size--;
//        }
//
//        size++;
//        addNodeToHead(dLinkedNode);
//        hashMap.put(key,dLinkedNode);
//    }
//
//
//    public void removeNode(DLinkedNode dLinkedNode){
//        dLinkedNode.pre.next = dLinkedNode.next;
//        dLinkedNode.next.pre = dLinkedNode.pre;
//    }
//
//
//    public void addNodeToHead(DLinkedNode dLinkedNode){
//        dLinkedNode.pre = head;
//        dLinkedNode.next = head.next;
//        head.next.pre = dLinkedNode;
//        head.next =dLinkedNode;
//    }
//}
